/*
 * xscanner.cpp
 *
 *  Created on: 2009-8-25
 *      Author: fanliangliang
 */

#include "xscanner.h"

#include <iostream>
#include <stack>

BEGIN_NAMESPACE_TOXIC

using namespace std;

static const CharSequence CHAR_SEQUENCES[CHAR_CLASS_COUNT] = {
	{ CHAR_WHITESPACE, " " },
	{ CHAR_SYMBOLS, "+-*/()" },
	{ CHAR_DIGIT, "0123456789" },
	{ CHAR_DOT, "." },
	{ CHAR_OTHER, 0 }
};


static CharClass typeOf(char ch) {
	foreach (const CharSequence& ts, CHAR_SEQUENCES) {
		if (ts.match(ch)) {
			return ts.type;
		}
	}
	return CHAR_OTHER;
}


#define _state(state, accept, advance) { (state & 0x3F) | (accept << 6) | (advance << 7) }
#define _state_error() { 0xFF }

static const ScanState TRANSITION_TABLE[5][CHAR_CLASS_COUNT] = {
	{ _state(1, 0, 1), _state(5, 1, 1), _state(2, 0, 1), _state_error(), _state_error() },
	{ _state(1, 0, 1), _state(6, 1, 0), _state(6, 1, 0), _state(6, 1, 0), _state(6, 1, 0) },
	{ _state(7, 1, 0), _state(7, 1, 0), _state(2, 0, 1), _state(3, 0, 1), _state(7, 1, 0) },
	{ _state_error(), _state_error(), _state(4, 0, 1), _state_error(), _state_error() },
	{ _state(8, 1, 0), _state(8, 1, 0), _state(4, 0, 1), _state(8, 1, 0), _state(8, 1, 0) }
};

#undef _state
#undef _state_error


using namespace std;

Scanner::Scanner(const string& str)
:_str(str)
,_pos(0)
,_eof(false) {

}

bool Scanner::hasNext() const {
	return !_eof;
}

char Scanner::currentChar() {
	return _eof ? 0xFF : _str[_pos];
}

char Scanner::nextChar() {
	if (_pos + 1 < _str.size()) {
		++_pos;
	}
	else {
		_eof = true;
	}
	return currentChar();
}

Token Scanner::next() {
	int index = 0;
	ScanState ss = { 0 };
	char ch = currentChar();
	while (!ss.accept() && !ss.error()) {
		ss = TRANSITION_TABLE[ss.state()][typeOf(ch)];
		if (_eof) {
			break;
		}
		if (ss.advance()) {
			if (index <= MAX_TOKEN_LENGTH) {
				_token[index++] = ch;
			}
			ch = nextChar();
		}
	}

	_token[index] = '\0';

	if (ss.error()) {
		cout << "[error token:" << _token << "][char:" << ch << "]" << endl;
		return Token(TOKEN_ERROR, _token);
	}

	return Token(TokenType(ss.state() - 5), _token);
}


static int expr_precedence(char op) {
	if (op == '^') {
		return 3;
	}
	else if (op == '*' || op == '/') {
		return 2;
	}
	else if (op == '+' || op == '-') {
		return 1;
	}
	else {
		return 0;
	}
}

static int expr_associative(char op) {
	return 0;
}

bool exprInfixToPostfix(string& postfix, const string& infix) {
	stack<char> opStack;

	foreach (char ch, infix) {
		if (std::isdigit(ch)) {
			postfix.push_back(ch);
		}
		else if (ch == '^' || ch == '+' || ch == '-' || ch == '*' || ch == '/') {
			while (!opStack.empty() && ((expr_associative(ch) == 0 && expr_precedence(ch) <= expr_precedence(opStack.top())) || (expr_associative(ch) == 1 && expr_precedence(ch) < expr_precedence(opStack.top())))) {
				postfix.push_back(opStack.top());
				opStack.pop();
			}
			opStack.push(ch);
		}
		else if (ch == '(') {
			opStack.push(ch);
		}
		else if (ch == ')') {
			while (!opStack.empty() && opStack.top() != '(') {
				postfix.push_back(opStack.top());
				opStack.pop();
			}
			if (!opStack.empty()) {
				opStack.pop();
			}
			else {
				//TODO: error: parentheses mismatched
				return false;
			}
		}
	}

	while (!opStack.empty()) {
		char topOp = opStack.top();
		if (topOp == '(') {
			return false;
		}
		postfix.push_back(topOp);
		opStack.pop();
	}

	return true;
}

END_NAMESPACE_TOXIC
